\batchmode
\makeatletter
\def\input@path{{/Users/sergei.winitzki/Code/talks/ftt-fp/}}
\makeatother
\documentclass[english]{beamer}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{3}
\usepackage{babel}
\usepackage{amsmath}
\ifx\hypersetup\undefined
  \AtBeginDocument{%
    \hypersetup{unicode=true,pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true}
  }
\else
  \hypersetup{unicode=true,pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true}
\fi

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 % this default might be overridden by plain title style
 \newcommand\makebeamertitle{\frame{\maketitle}}%
 % (ERT) argument for the TOC
 \AtBeginDocument{%
   \let\origtableofcontents=\tableofcontents
   \def\tableofcontents{\@ifnextchar[{\origtableofcontents}{\gobbletableofcontents}}
   \def\gobbletableofcontents#1{\origtableofcontents}
 }
 \newenvironment{lyxcode}
   {\par\begin{list}{}{
     \setlength{\rightmargin}{\leftmargin}
     \setlength{\listparindent}{0pt}% needed for AMS classes
     \raggedright
     \setlength{\itemsep}{0pt}
     \setlength{\parsep}{0pt}
     \normalfont\ttfamily}%
    \def\{{\char`\{}
    \def\}{\char`\}}
    \def\textasciitilde{\char`\~}
    \item[]}
   {\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usetheme[secheader]{Boadilla}
\usecolortheme{seahorse}
\title[Chapter 8: Applicative functors]{Chapter 8: Applicative functors and profunctors}
\subtitle{Part 1: Practical examples}
\author{Sergei Winitzki}
\date{2018-06-25}
\institute[ABTB]{Academy by the Bay}
\setbeamertemplate{headline}{} % disable headline at top
\setbeamertemplate{navigation symbols}{} % disable navigation bar at bottom
\usepackage[all]{xy}
\makeatletter
% Macros to assist LyX with XYpic when using scaling.
\newcommand{\xyScaleX}[1]{%
\makeatletter
\xydef@\xymatrixcolsep@{#1}
\makeatother
} % end of \xyScaleX
\makeatletter
\newcommand{\xyScaleY}[1]{%
\makeatletter
\xydef@\xymatrixrowsep@{#1}
\makeatother
} % end of \xyScaleY

\makeatother

\begin{document}
\frame{\titlepage}
\begin{frame}{Motivation for applicative functors}

\begin{itemize}
\item \vspace{-0.25cm}Monads are inconvenient for expressing \emph{independent}
effects
\end{itemize}
Monads perform effects \emph{sequentially} even if effects are independent:\texttt{\textcolor{blue}{\footnotesize{}\medskip{}
}}{\footnotesize \par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}x~$\leftarrow$~Future~\{~c1~\}}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}y~$\leftarrow$~Future~\{~c2~\}}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}z~$\leftarrow$~Future~\{~c3~\}}{\footnotesize \par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}Future~\{~c1~\}.flatMap~\{~x~$\Rightarrow$}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}~~Future~\{~c2~\}.flatMap~\{~y~$\Rightarrow$}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}~~~~Future~\{~c3~\}.map~\{~z~$\Rightarrow$~...\}}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}\}~\}}{\footnotesize \par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize \par}
\begin{itemize}
\item We would like to parallelize independent computations
\item We would like to accumulate \emph{all} errors, rather than stop at
the first one
\end{itemize}
Changing the order of monad's effects will (generally) change the
result:\texttt{\textcolor{blue}{\footnotesize{}\medskip{}
}}{\footnotesize \par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}~~x~$\leftarrow$~List(1,~2)}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}~~y~$\leftarrow$~List(10,~20)}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}\}~yield~f(x,~y)}{\footnotesize \par}

\textrm{\textcolor{gray}{\footnotesize{}//~f(1,~10),~f(1,~20),~f(2,~10),~f(2,~20)}}{\footnotesize \par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}~~y~$\leftarrow$~List(10,~20)}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}~~x~$\leftarrow$~List(1,~2)}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}\}~yield~f(x,~y)}{\footnotesize \par}

\textrm{\textcolor{gray}{\footnotesize{}//~f(1,~10),~f(2,~10),~f(1,~20),~f(2,~20)}}{\footnotesize \par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize \par}
\begin{itemize}
\item We would like to express a computation where effects are unordered
\begin{itemize}
\item This can be done using a method \texttt{\textcolor{blue}{\footnotesize{}map2}},
\emph{not} defined via \texttt{\textcolor{blue}{\footnotesize{}flatMap}}:
the desired type signature is {\footnotesize{}$\text{map2}:F^{A}\times F^{B}\Rightarrow\left(A\times B\Rightarrow C\right)\Rightarrow F^{C}$} 
\item \textbf{Applicative functor} has \texttt{\textcolor{blue}{\footnotesize{}map2}}
and \texttt{\textcolor{blue}{\footnotesize{}pure}} but is not necessarily
a monad
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Defining \texttt{\textcolor{blue}{\footnotesize{}map2}}, \texttt{\textcolor{blue}{\footnotesize{}map3}},
etc.}

\vspace{-0.15cm}Consider 1, 2, 3, ... commutative and independent
``effects''

\texttt{\textcolor{blue}{\footnotesize{}\hrule\medskip{}
}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{~x1~$\leftarrow$~c1}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}\}~yield~f(x1)}{\footnotesize \par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}c1.map(f)}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize \par}

\texttt{\textcolor{blue}{\footnotesize{}\hrule\medskip{}
}}{\footnotesize \par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{~x1~$\leftarrow$~c1}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}~~x2~$\leftarrow$~c2}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}\}~yield~f(x1,~x2)}{\footnotesize \par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}(c1,~c2).map2(f)}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
\hrule\medskip{}
}}{\footnotesize \par}

\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}for~\{~x~$\leftarrow$~c1}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}~~x2~$\leftarrow$~c2}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}~~x3~$\leftarrow$~c3}{\footnotesize \par}

\textcolor{blue}{\footnotesize{}\}~yield~f(x1,~x2,~x3)}{\footnotesize \par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}(c1,~c2,~c3).map3(f)}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
\hrule\medskip{}
}}{\footnotesize \par}
\begin{itemize}
\item Generalize from \texttt{\textcolor{blue}{\footnotesize{}map}}, \texttt{\textcolor{blue}{\footnotesize{}map2}},
\texttt{\textcolor{blue}{\footnotesize{}map3}} to \texttt{\textcolor{blue}{\footnotesize{}mapN}}:
\begin{align*}
\text{map}_{1} & :F^{A}\Rightarrow\left(A\Rightarrow Z\right)\Rightarrow F^{Z}\\
\text{map}_{2} & :F^{A}\times F^{B}\Rightarrow\left(A\times B\Rightarrow Z\right)\Rightarrow F^{Z}\\
\text{map}_{3} & :F^{A}\times F^{B}\times F^{C}\Rightarrow\left(A\times B\times C\Rightarrow Z\right)\Rightarrow F^{Z}
\end{align*}
\end{itemize}
\end{frame}

\begin{frame}{Practical examples of using \texttt{\textcolor{blue}{\footnotesize{}mapN}} }
\begin{itemize}
\item \vspace{-0.2cm}$F^{A}\equiv Z+A$ where $Z$ is a monoid: collect
all errors
\item $F^{A}=Z+A$: Create a validated case class out of validated parts
\item $F^{A}\equiv$ \texttt{\textcolor{blue}{\footnotesize{}Future{[}A{]}}}:
perform several computations concurrently
\item $F^{A}\equiv E\Rightarrow A$: pass standard arguments to functions
more easily
\item $F^{A}\equiv\text{List}^{A}$tem $F^{A}\equiv\text{List}^{A}$: transposing a matrix by using \texttt{\textcolor{blue}{\footnotesize{}map2}} 
\item Applicative contrafunctors and applicative profunctors
\begin{itemize}
\item defining an instance of \texttt{\textcolor{blue}{\footnotesize{}Semigroup}}
type class from \texttt{\textcolor{blue}{\footnotesize{}Semigroup}}
parts
\item implement \texttt{\textcolor{blue}{\footnotesize{}imap2}} for non-disjunctive
profunctors, e.g.\ $Z\times A\Rightarrow A\times A$
\end{itemize}
\item ``Fused \texttt{\textcolor{blue}{\footnotesize{}fold}}'': automatically
merge several \texttt{\textcolor{blue}{\footnotesize{}fold}}s into
one
\begin{itemize}
\item compute several running averages in one traversal (\href{https://github.com/amarpotghan/scala-fold}{scala-folds})
\end{itemize}
\item The difference between applicative and monadic functors
\begin{itemize}
\item define monadic folds using the ``free functor'' construction
\item compute running averages that depend on previous running averages
\begin{itemize}
\item do not confuse this with \emph{monad-valued} folds (\href{https://github.com/atnos-org/origami}{origami})!
\end{itemize}
\item applicative parsers vs.\ monadic parsers
\begin{itemize}
\item applicative: parse independent data, collecting all errors
\item monadic: parse depends on previous results, stops on errors
\end{itemize}
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Exercises I }

Implement \texttt{\textcolor{blue}{\footnotesize{}map2}}, or \texttt{\textcolor{blue}{\footnotesize{}imap2}}
if appropriate, for these type constructors $F^{A}$:
\begin{enumerate}
\item $F^{A}\equiv1+A+A\times A$
\item $F^{A}\equiv E\Rightarrow A\times A$
\item $F^{A}\equiv Z\times A\Rightarrow A$ 
\item $F^{A}\equiv A\Rightarrow A\times Z$ where $Z$ is a \texttt{\textcolor{blue}{\footnotesize{}Monoid}} 
\item Write a function that defines an instance of the \texttt{\textcolor{blue}{\footnotesize{}Monoid}}
type class for a tuple $\left(A,B\right)$ whose parts already have
a \texttt{\textcolor{blue}{\footnotesize{}Monoid}} instance.
\item Define a \texttt{\textcolor{blue}{\footnotesize{}Monoid}} instance
for the type $F^{S}$ where $F$ is an applicative functor that has
\texttt{\textcolor{blue}{\footnotesize{}map2}} and \texttt{\textcolor{blue}{\footnotesize{}pure}},
while $S$ is itself a monoid type.
\item Define a ``regexp extractor'' as a type constructor $R^{A}$ describing
extraction of various data from strings; the extracted data is converted
to a value of type \texttt{\textcolor{blue}{\footnotesize{}Option{[}A{]}}}.
Implement \texttt{\textcolor{blue}{\footnotesize{}zip}} and \texttt{\textcolor{blue}{\footnotesize{}map2}}
for $R^{A}$.
\item Use parser combinators to implement an evaluator for arithmetic language
containing integers and $+$ symbols, for example $1+321+20$.
\item Use folding combinators to implement a \texttt{\textcolor{blue}{\footnotesize{}Fold}}
that computes the standard deviation of a sequence in one traversal.
\end{enumerate}
\end{frame}

\end{document}
